package com.labuladong.dataStruct;


public class MaxPQ<Key extends Comparable<Key>> {
    // 存储元素的数组
    private Key[] pq;

    // 当前Priority Queue中的元素个数
    private int N = 0;

    public MaxPQ(int cap) {
        // 索引0 不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    //    返回当前队列中最大元素
    public Key max() {
        return pq[1];
    }

    //    插入元素e
    public void insert(Key e) {
        N++;
        //  先把新元素加到最后
        pq[N] = e;

        // 让其上浮到正确位置
        swim(N);
    }

    //    删除并返回当前队列中最大元素
    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];

        // 把这个最大元素换到最后，删除之
        exchange(1, N);

        pq[N] = null;

        N--;

        // 让pq[1]下沉到正确位置
        sink(1);

        return max;
    }

    //    上浮第k个元素，以此维护最大堆性质
    private void swim(int k) {

        if (k > N) {
            // 不符合要求的输入
            return;
        }
        //  如果浮到了堆顶，就不能再上浮
        while (k > 1 && isLess(parent(k), k)) {
            //   如果第k个元素比上层大，就浮上去
            exchange(parent(k), k);
            k = parent(k);
        }
    }

    // 下沉第k个元素，以此维护最大堆性质
    private void sink(int k) {
        // 如果沉到底，就沉不下去了
        while (left(k) <= N) {
            // 假设左边节点比较大
            int bigger = left(k);

            // 如果右边节点存在，比较一下大小
            if (right(k) <= N && isLess(bigger, right(k))) {
                bigger = right(k);
            }

            // 节点k比两个孩子都大，不用下沉了
            if (isLess(bigger, k)) break;

            // 否则，不符合最大堆的结构，下沉k节点
            exchange(k, bigger);

            k = bigger;
        }
    }

    //    交换数组的两个元素
    private void exchange(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    //    比较大小  i是否比j小？
    private boolean isLess(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }


    private int parent(int root) {
        return root / 2;
    }

    private int left(int root) {
        return root * 2;
    }

    private int right(int root) {
        return root * 2 + 1;
    }

    //    获得父节点
    private Key parentNode(int k) {
        return pq[k / 2];
    }

    // 获得左子结点
    private Key leftNode(int k) {
        return k * 2 > N ? pq[k * 2] : null;
    }

    // 获得右节点
    private Key rightNode(int k) {
        return k * 2 + 1 > N ? pq[k * 2 + 1] : null;
    }

    // 从一个数组 自顶向下建堆
    // 自顶向下建堆的思想是，从第 i=1 个元素开始，对其进行向上调整，始终使前 i 个元素保持堆的结构。时间复杂度 O(nlogn)
    public Key[] ArrayToPQ(Key[] a) {
        N = a.length;
        pq = a;

        for (int i = 1; i <= N; i++) {
            // 向上调整 上浮
            swim(i);
        }
        return pq;
    }

    // 从一个数组  自底向上建堆
    // 自底向上建堆的思想是，从底 i=⌊n/2⌋ 个元素开始，对其进行向下调整，始终让后 n−i 个元素保持堆的结构。
    public Key[] ArrayToBPQ(Key[] a) {
        N = a.length;
        pq = a;

        int i = N / 2;
        for (; i >= 1; i--) {
            sink(i);
        }

        return pq;
    }

    // 堆排序 输入乱序数组 输出有序数组
    public Key[] heapSort(Key[] arr) {
        // 先自底向上建堆
        ArrayToBPQ(arr);

        // 然后将最大堆变成降序数组
        for (int i = N; i > 1; i++) {
            exchange(1, i);
            sink(i - 1);
        }

        return pq;
    }
}
